1. Field of Invention
The present invention relates to retransmission timeout (RTO) estimators, and particularly, to a system and method for estimating RTO in the NACK-based real-time streaming applications that support multiple re-transmission of the same packet.
2. Description of the Invention
In general, there are two types of Internet transport protocols that support lost packet recovery in a data communication network. The first approach is ACK-based as set forth under the transmission control protocol (TCP), which involves the receiver sending a positive acknowledgment (ACK) in response to each received packet. The second approach is NACK-based under a user datagram protocol (UDP), which involves the receiver sending a negative acknowledgment (NACK) in response to each lost packet.
Referring to FIG. 1(a), TCP utilizes a system of positive acknowledgments (ACK) for data arriving to the receiving endpoint as the mechanism for error recovery. This system operates under the principle that only unacknowledged frames should be retransmitted. To ensure that the packet is safely received by the sending source, TCP uses a retransmission timeout (RTO) mechanism by managing a retransmission timer for each connection. That is, TCP sets the retransmission timer and tacks an RTO value and a round trip time (RTT) for the connection. The RTT is the time elapsed between the start of transmission of a TCP-type data segment and the receipt of an acknowledgment of that segment. If an acknowledgment is not received by the time the RTO1 expires, TCP retransmits the data again within next the RTO2.
In contrast, UDP utilizes a system of negative acknowledgments (NACK) by forwarding a NACK packet to the sending source in response to the lost frame for retransmission, as shown in FIG. 1(b). In addition, the NACK packet can be lost along the path from the receiver to the sender. To this end, UDP utilizes a retransmission timeout mechanism that is similar to the TCP for retransmission connection.
It is important that the estimation of an RTO value is performed accurately. Normally, the RTO estimation is performed by predicting the next value of the RTT based on the previous samples of the RTTs. If the RTO is overestimated, it leads to lower throughput performance in TCP and may cause an increased number of under-flow events in real time application. Yet, if the RTO is underestimated, the protocol generates a large number of duplicate packets that cause serious network congestion as more of unnecessary packets are retransmitted.
A background of current standards, which is based on TCP's retransmission timeout estimator, is described hereinafter. The standard consists of two algorithms described below. The first algorithm, smoothed RTT estimator (SRTT), is based on an exponential-weighed moving average (EWMA) of the past RTT samples:                               SRTT          i                =                  {                                                                                          RTT                    0                                    ,                                      i                    =                    0                                                                                                                                                                                          (                                                  1                          -                          •                                                )                                            ·                                              SRTT                                                  i                          -                          1                                                                                      +                                          •                      ·                                              RTT                        i                                                                              ,                                      i                    ≥                    1                                    ,                                                                                        (        1        )            
where RTTi represents the i-th sample of the round-trip delay produced at time ti and □ (set by default to ⅛) represents a smoothing factor that can be varied to give more or less weight to the history of RTT samples.
The second algorithm, smoothed RTT variance estimator (SVAR), computes an approximation to the RTT variance using similar EWMA formulas to the ones described above:                               SVAR          i                =                  {                                                                                                                RTT                      0                                        /                    2                                    ,                                      i                    =                    0                                                                                                                                                                                          (                                                  1                          -                          β                                                )                                            ·                                              SVAR                                                  i                          -                          1                                                                                      +                                          β                      ·                                              VAR                        i                                                                              ,                                      i                    ≥                    1                                    ,                                                                                        (        2        )            
where β (set by default to ¼) represents an EWMA smoothing factor and VARl represents the absolute deviation of the i-th RTT sample from the smoothed average: VARt=|SRTTt−1−RTTi|.
Finally, the RTO is determined by multiplying the smoothed variance by four and adding it to the smoothed round-trip delay:RTO(t)=SRTTi+4·SVARi,  (3)
where t represents the time at which the RTO is computed, and i=max:ti≦t.
In real-time streaming applications, e.g., multimedia applications, NACK-based operation is preferred due to a lower overhead along the path from the receiver to the sender and potentially faster recovery of lost packets. However, the RTO estimator, as described in the preceding paragraphs, is typically suitable only for the ACK-based applications and is not applicable to NACK-based protocols by design. It produces an extended number of duplicate packets and causes unnecessary delays in the generation of the subsequent NACK requests in real-time streaming applications due to poor prediction of the next RTT value. In addition, NACK-based protocols do not have a common RTO estimation scheme that works well in heterogeneous Internet conditions. Despite these drawbacks, many NACK-based protocols are still utilizing the existing RTO estimating protocol, which is borrowed from TCP.
As described above, an RTO estimator is described by two parameters—the number of duplicate packets and the amount of unnecessary time out waiting. However, these two parameters cannot be minimized at the same time as they represent a basic trade-off of the estimator (i.e., decreasing one parameter will increase the other). Since TCP's RTO estimator proves to be inapplicable in NACK-based protocol, there is a need for such protocols to employ the class of optimal RTO estimators, which are described in this patent disclosure.